# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def isBalanced(self, root: TreeNode) -> bool:
        try:
            self.__getBBTHeight(root)
            return True
        except ValueError as e:
            return False

    def __getBBTHeight(self, node: TreeNode) -> int:
        if node is None:
            return 0
        if node.left == None and node.right == None:
            return 1
        lheight = self.__getBBTHeight(node.left)
        rheight = self.__getBBTHeight(node.right)
        diff = lheight - rheight
        if diff > 1 or diff < -1:
            raise ValueError('not a bbt')
        return max(lheight, rheight) + 1

n3 = TreeNode(3)
n7 = TreeNode(7)
n9 = TreeNode(9)
n15 = TreeNode(15)
n20 = TreeNode(20)
n3.left = n9
n3.right = n20
n20.left = n15
n20.right = n7

t1 = TreeNode(1)
tl2 = TreeNode(2)
tr2 = TreeNode(2)
t1.left = tl2
t1.right = tr2
tl3 = TreeNode(3)
tr3 = TreeNode(3)
tl2.left = tl3
tl2.right = tr3
tl4 = TreeNode(4)
tr4 = TreeNode(4)
tl3.left = tl4
tl3.right = tr4

solu = Solution()
print("{0}".format(solu.isBalanced(n3)))
print("{0}".format(solu.isBalanced(t1)))